(0) Obligation:
Runtime Complexity Relative TRS:
The TRS R consists of the following rules:
loop(Cons(x, xs), Nil, pp, ss) → False
loop(Cons(x', xs'), Cons(x, xs), pp, ss) → loop[Ite](!EQ(x', x), Cons(x', xs'), Cons(x, xs), pp, ss)
loop(Nil, s, pp, ss) → True
match1(p, s) → loop(p, s, p, s)
The (relative) TRS S consists of the following rules:
!EQ(S(x), S(y)) → !EQ(x, y)
!EQ(0, S(y)) → False
!EQ(S(x), 0) → False
!EQ(0, 0) → True
loop[Ite](False, p, s, pp, Cons(x, xs)) → loop(pp, xs, pp, xs)
loop[Ite](True, Cons(x', xs'), Cons(x, xs), pp, ss) → loop(xs', xs, pp, ss)
Rewrite Strategy: INNERMOST
(1) DecreasingLoopProof (EQUIVALENT transformation)
The following loop(s) give(s) rise to the lower bound Ω(n1):
The rewrite sequence
loop(Cons(0, xs'), Cons(0, xs), pp, ss) →+ loop(xs', xs, pp, ss)
gives rise to a decreasing loop by considering the right hand sides subterm at position [].
The pumping substitution is [xs' / Cons(0, xs'), xs / Cons(0, xs)].
The result substitution is [ ].
(2) BOUNDS(n^1, INF)